#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

#define MAXN 6  

int n = 5;
double W = 100;
struct NodeType {
    double w;
    double v;
    double p;
    bool operator<(const NodeType &s) const {
        return p > s.p;  
    }
};

NodeType A[MAXN + 1] = { {0}, {10, 20}, {20, 30}, {30, 66}, {40, 40}, {50, 60}};
double V;
double x[MAXN + 1];

void dispA() {
    for (int i = 1; i <= n; i++) {
        printf("w=%g, v=%g, p=%g\n", A[i].w, A[i].v, A[i].p);
    }
}

void Knp() {
    V = 0;
    double weight = W;
    memset(x, 0, sizeof(x));
    for (int i = 1; i <= n; i++) {
        if (A[i].w <= weight) {
            x[i] = 1;
            weight -= A[i].w;
            V += A[i].v;
        } else if (weight > 0) {
            x[i] = weight / A[i].w;
            V += x[i] * A[i].v;
            break; 
        }
    }
}

int main() {
    printf("求解过程\n");
    for (int i = 1; i <= n; i++) {
        A[i].p = A[i].v / A[i].w;
    }
    printf("(1)排序前\n");
    dispA();
    sort(A + 1, A + n + 1);
    printf("(2)排序后\n");
    dispA();
    Knp();
    printf("(3)求解结果\n");
    printf("x:[");
    for (int j = 1; j <= n; j++) {
        printf("%g,", x[j]);
    }
    printf("]\n");
    printf("总价值=%g\n", V);

    return 0;
}